package com.yun.datastructure.linear.queue;

import java.util.LinkedList;

public class leetcode239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        MonotonicQueue queue = new MonotonicQueue();
        for (int i = 0; i < k - 1; i++) {
            int num = nums[i];
            queue.offer(num);
        }
        for (int i = k - 1; i < nums.length; i++) {
            if (i >= k && queue.peek() == nums[i - k]) {
                queue.poll();
            }
            int num = nums[i];
            queue.offer(num);
            res[i - k + 1] = queue.peek();
        }
        return res;
    }

    static class MonotonicQueue {
        private LinkedList<Integer> deque = new LinkedList<>();

        public Integer peek() {
            return deque.peekFirst();
        }

        public void poll() {
            deque.pollFirst();
        }

        public void offer(Integer t) {
            while (!deque.isEmpty() && deque.peekLast() < t) {
                deque.pollLast();
            }
            deque.offerLast(t);
        }
    }
}
